package leetcode_2601_2700;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_2699 {
    public static void main(String[] args) {

    }
    private static int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        List<int[]>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int[] e = edges[i];
            g[e[0]].add(new int[]{e[1], i}); //建图, 记录额外边的编号
            g[e[1]].add(new int[]{e[0], i});
        }

        //最短路结果表
        int[][] dis = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i != source){
                dis[i][0] = dis[i][1] = Integer.MAX_VALUE;
            }
        }

        //第一次dij
        dijkstra(g, edges, destination, dis, 0, 0);
        int delta = target - dis[destination][0];
        if (delta < 0){ //-1全改成1仍然小于target
            return new int[][]{};
        }

        //第二次dij
        dijkstra(g, edges, destination, dis, delta, 1);
        if (dis[destination][1] < target){ //最短路无法再变大
            return new int[][]{};
        }
        for (int[] e : edges) {
            if (e[2] == -1){
                e[2] = 1;
            }
        }
        return edges;
    }

    private static void dijkstra(List<int[]>[] g, int[][] edges, int destination, int[][] dis, int delta, int k){
        int n = g.length;
        boolean[] vis = new boolean[n];
        for(;;){
            int x = -1;
            for (int i = 0; i < n; i++) {
                if (!vis[i] && (x < 0 || dis[i][k] < dis[x][k])){
                    x = i;
                }
            }
            if (x == destination){
                return;
            }
            vis[x] = true;
            for (int[] e : g[x]) {
                int eid = e[1], y = e[0];
                int wt = edges[eid][2];
                if (wt == -1){
                    wt = 1;
                }
                if (k == 1 && edges[eid][2] == -1){
                    int w = delta + dis[y][0] - dis[x][1];
                    if (w > wt){
                        edges[eid][2] = wt = w;
                    }
                }
                dis[y][k] = Math.min(dis[y][k], dis[x][k] + wt);
            }
        }
    }
}
